package org.mango.dsaa.demo;

/**
 * 编写的五子棋程序中，有存盘退出和续上盘的功能。
 * 因为该二维数组的很多值是默认值0，因此记录了很多没有意义的数据，为了压缩存储所以采用稀疏数组。
 * 8 x 8的棋盘，1表示黑子，2表示白子
 */
public class SparseArrayDemo {
    /**
     *
     * 原数组为：
     * 0	0	0	0	0	0	0	0
     * 0	0	1	0	0	0	0	0
     * 0	0	0	2	0	0	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	1	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	0	0	0
     * 原数组共8行8列，3个不为0的值
     * 稀疏数组为：
     * 8	8	3
     * 1	2	1
     * 2	3	2
     * 5	5	1
     * 从稀疏数组还原如下：
     * 0	0	0	0	0	0	0	0
     * 0	0	1	0	0	0	0	0
     * 0	0	0	2	0	0	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	1	0	0
     * 0	0	0	0	0	0	0	0
     * 0	0	0	0	0	0	0	0
     */
    public static void main(String[] args){
        int row = 8,col = 8;
        int[][] arr = new int[row][col];
        arr[1][2] = 1;
        arr[2][3] = 2;
        arr[5][5] = 1;

        // 先遍历原始数组，得到不为0的元素个数
        System.out.println("原数组为：");
        int count = 0;
        for(int[] rowArr : arr){
            for(int colVal : rowArr){
                if(colVal != 0)
                    count++;
                System.out.printf("%d\t",colVal);
            }
            System.out.println();
        }
        System.out.printf("原数组共%d行%d列，%d个不为0的值",row,col,count);
        System.out.println();
        //创建稀疏数组，3列，count+1行
        SparseArray sa = new SparseArray(count+1);
        sa.add(0,0,row);
        sa.add(0,1,col);
        sa.add(0,2,count);

        int saRowIndex = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(arr[i][j] != 0) {
                    saRowIndex++;
                    sa.add(saRowIndex,0,i);
                    sa.add(saRowIndex,1,j);
                    sa.add(saRowIndex,2,arr[i][j]);
                }
            }
        }
        System.out.println("稀疏数组为：");
        sa.show();
        System.out.println("从稀疏数组还原如下：");
        int[][] rbArr = sa.rebuild();
        for(int[] rowArr : rbArr){
            for(int colVal : rowArr){
                System.out.printf("%d\t",colVal);
            }
            System.out.println();
        }
    }


}
//稀疏数组
class SparseArray {
    private int[][] arr;//二维数组

    public SparseArray(int row){
        this.arr = new int[row][3];//初始化数组
    }

    public void add(int row,int col,int val){
        this.arr[row][col] = val;
    }

    public void show(){
        for(int[] rowArr : arr){
            for(int colVal : rowArr){
                System.out.printf("%d\t",colVal);
            }
            System.out.println();
        }
    }

    public int[][] rebuild(){
        int[][] rbArr = new int[arr[0][0]][arr[0][1]];
        int count = arr[0][2];
        for(int i=1;i<=count;i++){
            rbArr[arr[i][0]][arr[i][1]] = arr[i][2];
        }
        return rbArr;
    }

}
